Fix PR#22427. The implementation of inplace_merge had a \'small data set\' optimization; if either half of the merge was small (i.e, less than 9 items), it did an inplace merge rather than allocating a buffer and doing a faster/smarter merge. However, this failed to satisfy the complexity requirements in the standard. Remove that code. Add tests to check the complexity, and add the same tests for std::merge, since we are in that section of the test suite anyway. git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@227811 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/algorithm b/include/algorithm index a179acf..9c51284 100644 --- a/include/algorithm +++ b/include/algorithm
@@ -4482,12 +4482,6 @@ } } -template <class _Tp> -struct __inplace_merge_switch -{ - static const unsigned value = is_trivially_copy_assignable<_Tp>::value; -}; - template <class _BidirectionalIterator, class _Compare> inline _LIBCPP_INLINE_VISIBILITY void @@ -4499,13 +4493,9 @@ difference_type __len1 = _VSTD::distance(__first, __middle); difference_type __len2 = _VSTD::distance(__middle, __last); difference_type __buf_size = _VSTD::min(__len1, __len2); - pair<value_type*, ptrdiff_t> __buf(0, 0); - unique_ptr<value_type, __return_temporary_buffer> __h; - if (__inplace_merge_switch<value_type>::value && __buf_size > 8) - { - __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); - __h.reset(__buf.first); - } + pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); + unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); + #ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); 